For each combinatoric computing problem which focuses on finding an appropriate value assignment for the variables in the problem, a corresponding decision problem can be constructed which seeks a YES-NO answer as to whether a candidate assignment for the variables is actually a solution to the combinatoric problem. Nondeterministic Polynomial Time complete (NP-complete) decision problems are those for which no efficient solution method is known, in the sense that the number of steps in the solution method is a polynomial function of the size of the smallest representation of the problem (referred to as xe2x80x9cpolynomial-timexe2x80x9d), but for which a candidate guess of the solution can be checked in polynomial time. It is known that all NP-complete problems are polynomial-time Karp-reduction equivalent, i.e., any instance of a particular NP-complete problem can be mapped in a polynomial time into an instance of some other NP-complete problem such that the solutions of this problem correspond to solutions of the original problem under the mapping.
Randomized computing methods incorporate probabilistic decision making techniques in addition to deterministic techniques and provide a solution to the problem which is correct with some minimum and selectable probability. Although it is believed that no deterministic, polynomial-time solution method exists for NP-Complete problems, it is known that the class PP of decision problems solvable in polynomial time by randomized computing methods includes the NP-complete problems. See xe2x80x9cStructural Complexity Ixe2x80x9d by J. L. Balcazar, J. Diaz and J. Gabarro.
In the prior art, simulated annealing methods so-called Boltzmann machines have been referred to as randomized computing systems. See xe2x80x9cOptimization by Simulated Annealingxe2x80x9d by S. Kirkpatrick, C. D. Gelett and M. P. Vecchi; xe2x80x9cA Thermodynamic Approach to the Traveling Salesman Problem: An Efficient Simulationxe2x80x9d by V. Cerny, and xe2x80x9cBoltzmann Machines: Constraint Satisfaction Networks that Learnxe2x80x9d by G. E. Hinton, T. J. Sejnowski and D. H. Ackley. These methods differ from the present invention, however, in that they are more properly identified as heuristic methods for solving combinatorial computing problems. Although some versions of these methods do incorporate probabilistic decision techniques, the solutions they provide in polynomial-time are not guaranteed to be correct with some minimum selectable probability. The prior art does not appear to include any computing systems which efficiently realize randomized computing methods in the formal rigorous sense defined above.
The probabilistic computing system (PCS) of the present invention provides the computational functionality needed to efficiently realize randomized computing methods in otherwise standard, deterministic digital computing systems. The PCS may be incorporated in a standard computing platform such as a PC in various ways. For example, for applications requiring moderate performance, a VLSI probabilistic computation network chip, further described below, can be combined with standard dynamic RAMs and used as a memory-mapped peripheral. In such a configuration, multiple PCS-DRAM modules can be interconnected for increased processing power. For higher performance applications, a peripheral device analogous to a mass memory peripheral (for example a hard disk) can be constructed by combining multiple PCS chips with dynamic RAM and interface logic. The disclosed invention allows solution of computing problems that heretofore could not be practically solved in small systems.
A probabilistic computing system according to the invention includes a memory for receiving and storing a digital representation of a predetermined combinatorial computing problem. The problem is expressed as a series of clauses in conjunctive normal form. In the preferred embodiment, the memory includes a plurality of rows of memory cells, each row arranged for storing a series of data bits corresponding to a respective clause of the computing problem. Each row stores a series of pairs of bits, each bit pair corresponding to a respective one of the variables and its logical complement.
A nondeterministic logic subsystem is provided for generating a set of random boolean values of the variables as a first proposed solution to the stored computing problem. Testing circuitry is coupled to the memory and to the nondeterministic logic means for testing whether the first set of random boolean values satisfies the stored computing problem. Finally, a feedback circuit couples the testing circuit and to the nondeterministic logic subsystem for controlling the ND subsystem so as to generate an alternative set of random boolean values of the series of variables as an alternative proposed solution to the computing problem whenever the testing circuit indicates that the computing problem is not satisfied. Thus the nondeterministic subsystem, the testing circuit and the feedback circuit together form a hardware loop for asynchronous operation. The system preferably is run asynchronously to maximize speed.
The nondeterministic subsystem includes a series of semiconductor nondeterministic logic elements. Each ND logic element includes a cross-coupled pair of inverting gates arranged for generating a respective one of the random boolean values of the series of variables, responsive to the variety of noise sources intrinsic to VLSI circuits.
The testing circuit includes, for each row of the memory means, a wide xe2x80x9cprogrammablexe2x80x9d NOR gate. The NOR gate provides a computed function signal (Cn) that indicates whether the proposed series of random boolean values satisfies the corresponding clause of the computing problem. Each bit of the data stored in the memory determines whether or not a corresponding one of the variables is included as an input to the NOR gate. In this way, the NOR gate is programmed to reflect the clause of the problem stored in that row of the memory.
Thus, the first wide NOR gate may be considered as part of a crosspoint switch array overlying the memory. The crosspoint switch array includes a series of crosspoint switch circuits, each crosspoint switch circuit being coupled to a respective bit of the corresponding row of the memory. Each crosspoint switch circuit also receives the corresponding variable signal from the corresponding ND logic element. In operation, each crosspoint switch circuit couples the corresponding probabilistic variable signal to a common circuit nodexe2x80x94the NOR gate inputxe2x80x94only if the said respective bit has a first predetermined logic state.
Accordingly, the programmable NOR gate in each row asserts the corresponding computed function signal responsive to such of the probabilistic variable signals as are coupled to the NOR input by the crosspoint switch circuits so as to indicate whether the first series of random probabilistic variable values satisfies the corresponding clause of the computing problem.
A second wide NOR gate is coupled to receive all of the computed function signals (C1-Cq) for determining and indicating whether the proposed solution satisfies the computing problem. This is true only when all of the computed function signals indicate that the corresponding clauses of the problem are satisfied. Accordingly, the second NOR gate has a number of inputs at least equal to the number of clauses in the computing problem. The output of the second NOR gate is used in the feedback circuit to trigger another set of values if the problem is not yet satisfied. A delay circuit in the feedback circuit provides for writing intermediate results to a DRAM.
The foregoing and other objects, features and advantages of the invention will become more readily apparent from the following detailed description of a preferred embodiment which proceeds with reference to the drawings.